package com.xhh.learning.record.algorithm.search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 类名： BFS
 * 描述： Breadth-First-Search 广度优先搜索
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/6/10 10:23
 * 最后修改时间:  2019/6/10 10:23
 */
public class BFS {

    static class Graph{
        int v;
        LinkedList<Integer>[] adj;

        public Graph(int v) {
            this.v = v;
            LinkedList[] list = new LinkedList[v];
            for (int i = 0; i < list.length; i++) {
                list[i] = new LinkedList();
            }
            this.adj = list;
        }

        public void addEdge(int start, int end) {
            adj[start].add(end);
            adj[end].add(start);
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(2, 1);
        graph.addEdge(4, 1);
        graph.addEdge(4, 3);
        graph.addEdge(4, 5);
        graph.addEdge(4, 6);
        graph.addEdge(2, 7);
        graph.addEdge(5, 7);
        graph.addEdge(6, 7);

        bfs(graph, 0, 6);

    }

    public static void bfs(Graph g, int s, int t) {
        boolean[] visited = new boolean[g.v];
        int[] prev = new int[g.v];
        for (int i = 0; i < g.v; i++) {
            prev[i] = -1;
        }
        visited[s] = true;
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(s);

        while (queue.size() > 0) {
            Integer w = queue.poll();
            LinkedList<Integer> list = g.adj[w];
            if (list.size() > 0) {
                for (int i = 0; i < list.size(); i++) {
                    Integer q = list.get(i);
                    if (!visited[q]) {
                        prev[q] = w;
                        if (q == t) {
                            print(prev, s, t);
                        }

                        visited[q] = true;
                        queue.add(q);
                    }
                }
            }
        }
    }

    public static void print(int[] prev, int s, int t) {
        if (prev[t] != -1 && s != t) {
            print(prev, s, prev[t]);
        }
        System.out.print(t + " ");
    }
}
